package com.cqs.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lixiaowen
 * @create 2019-12-12
 */
public class CanPlaceFlowers {

    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        if (n == 0) return true;
        if (flowerbed == null || flowerbed.length == 0) return false;
        int num = 0;
        //按照1进行分割
        int c = -1;
        while (++c < flowerbed.length) {
            if (flowerbed[c] == 1) {
                //判断是第一段0
                if ((c - num) == 0) {
                    num++;//逻辑上补充1
                }
                //可以种植的花的个数
                n -= (num - 1) / 2;
                if (n <= 0) return true;
                num = 0;
            } else {
                //计算0的个数
                ++num;
            }
        }
        //1.数组全是0
        if (num == flowerbed.length) {
            return (num + 1) / 2 >= n;
        }
        //2.处理最后一段0
        return n <= num / 2;
    }

    public boolean canPlaceFlowers0(int[] flowerbed, int n) {
        if (n == 0) return true;
        if (flowerbed == null || flowerbed.length == 0) return false;
        int num = 0;
        List<Integer> list = new ArrayList<>();
        //按照1进行分割
        int c = -1;
        while (++c < flowerbed.length) {
            if (flowerbed[c] == 1) {
                list.add(num);
                num = 0;
            } else {
                //计算0的个数
                ++num;
            }
        }
        list.add(num);
        //处理两端的0的个数
        if (list.size() == 0) return false;
        if (list.size() == 1) {
            return (list.get(0) + 1) / 2 >= n;
        } else {
            //预处理收尾两段
            for (int i = 0; i < list.size(); ++i) {
                int fn = list.get(i);
                if ((i == 0) || (i == list.size() - 1)) {
                    fn++;
                }
                n -= (fn - 1) / 2;
                if (n <= 0) return true;
            }
        }
        return n <= 0;
    }

    public static void main(String[] args) {
        CanPlaceFlowers flowers = new CanPlaceFlowers();
        int[] flow = {0, 1, 0, 0, 0, 0, 1};
        int n = 2;
        System.out.println(flowers.canPlaceFlowers(flow, n));
    }
}
